// @algorithm @lc id=31 lang=cpp 
// @title next-permutation


#define print(...)
// @test([1,2,3])=[1,3,2]
// @test([3,2,1])=[1,2,3]
// @test([1,1,5])=[1,5,1]
// @test([1])=[1]
class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        if(nums.size()<=1) return;
        print("nums=", nums, "\r\n")
        auto turn = nums.end()-1;
        while(turn!=nums.begin())
        {
            if(*(turn-1) < *turn){
                auto right=nums.end()-1;
                while(*(turn-1) >= *right) right--;
                swap(*(turn-1), *right);
                print("turn=", turn-nums.begin(),", right=", right-nums.begin(), "\r\n")
                break;
            }
            turn--;// [turn, end) 降序
        }
        // [turn, end) 必为降序, 将其翻转
        reverse(turn, nums.end());
    }
};